백준 1389번 - 케빈 베이컨의 6단계 법칙

문제링크

풀이과정

가중치가 1이기 때문에 BFS로도 문제를 풀 수 있다.

노드의 범위가 100 이하이기 때문에 짧은 코드인 플로이드-워셜 을 사용하기로 했다.

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
  input.push(line);
});

rl.on("close", () => {
  const [n, m] = input[0].split(" ").map((x) => parseInt(x));

  const arr = Array.from(Array(n), () => Array(n).fill(1e9));

  for (let i = 0; i < m; i++) {
    const [x, y] = input[i + 1].split(" ").map((x) => parseInt(x));
    arr[x - 1][y - 1] = 1;
    arr[y - 1][x - 1] = 1;
  }
  for (let i = 0; i < n; i++) {
    arr[i][i] = 0;
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }
  let min = { idx: 0, v: 1e9 };
  for (let i = 0; i < n; i++) {
    const sum = arr[i].reduce((acc, cur) => {
      return (acc += cur);
    }, 0);
    if (min.v > sum) {
      min.idx = i;
      min.v = sum;
    }
  }
  console.log(min.idx + 1);

  process.exit();
});

테스트케이스는 통과했지만 문제는 틀렸다

원인은 반복에 있었다.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
        // 아래 처럼 외각 for문을 잡고 돌면 틀린다.
        //arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }

최외각 for문을 기준으로 반복을 수행하면 틀린다.
왜 그럴까?
예를 들어 i가 1이고 j가 2일 때 arr[i][j] 는 1번 노드 부터 2번 노드 까지의 거리를 의미한다. 1번 노드와 2번 노드 중간다리인 k를 n 번 반복하면서 arr[1][2] 업데이트를 전체적으로 먼저하면 1번 노드에서 K 노드, k 노드에서 2번 노드 거리가 추후에 더 짧아졌을 경우를 포함시킬 수가 없기때문이다.
그래서 k 를 고정시켜놓고 i,j를 먼저 돌아야한다.